Benvenuti alla Lezione 3 di Concetti di Intelligenza Artificiale (PolyU COMP5511). In questa sessione, passiamo dal pathfinding a agente singolo alla Ricerca Avversariale, dove gli agenti operano in ambienti multi-agente competitivi. Introduciamo inoltre i Problemi di Soddisfacimento dei Vincoli (CSP), un paradigma in cui l'obiettivo è trovare uno stato che soddisfi un insieme specifico di restrizioni anziché un percorso.
Concetti Fondamentali
- Ricerca Avversariale: Si concentra su algoritmi come Minimax e Potatura Alfa-Beta per prendere decisioni razionali contro un avversario intelligente.
- Monte Carlo Tree Search (MCTS): Esplora il processo decisionale probabilistico, fungendo da spina dorsale per le moderne IA di gioco come AlphaGo.
- Soddisfacimento dei Vincoli: Modella i problemi utilizzando Variabili, Domini e Vincoli, risolti tramite Backtracking e Ricerca Locale.
Analisi della Complessità
In contesti avversariali, la complessità dello spazio di ricerca è spesso definita dal fattore di ramificazione del gioco
Avviso di Cambiamento di Paradigma
A differenza della ricerca standard (es. A* o BFS) in cui l'ambiente è statico, la Ricerca Avversariale presuppone che l'ambiente (l'avversario) tenti attivamente di ridurre al minimo il tuo successo. Nei CSP, l'ordine delle azioni conta meno della validità dell'assegnazione finale.
Pseudocodice Concettuale: Tipi di Agenti
1
# Adversarial Agent (Game Theory)
2
functionDecide_Move(state):
3
returnMaximize_Utility(Predict_Opponent_Minimization(state))
4
5
# CSP Solver (Constraint Logic)
6
functionSolve_CSP(variables, constraints):
7
ifAll_Constraints_Satisfied(assignment):
8
returnassignment
9
else:
10
returnBacktrack_Search(variables)
Course Roadmap
Transitioning from Search (Lesson 2) to Strategic Decision Making (Lesson 3).